package subject;

public class pathSum {
    public static void main(String[] args) {

    }

//    public int pathSum(TreeNode root, int targetSum) {
//        if (root == null) {
//            return 0;
//        }
//
//        int ret = rootSum(root, targetSum);
//        ret += pathSum(root.left, targetSum);
//        ret += pathSum(root.right, targetSum);
//        return ret;
//    }
//
//    public int rootSum(TreeNode root, long targetSum) {
//        int ret = 0;
//
//        if (root == null) {
//            return 0;
//        }
//        int val = root.val;
//        if (val == targetSum) {
//            ret++;
//        }
//
//        ret += rootSum(root.left, targetSum - val);
//        ret += rootSum(root.right, targetSum - val);
//        return ret;
//    }


//    class Solution {
//        public int pathSum(TreeNode root, int targetSum) {
//            Map<Long, Integer> prefix = new HashMap<Long, Integer>(); // 存储前缀和及其出现次数
//            prefix.put(0L, 1); // 初始化：前缀和为0的路径（空路径）出现1次
//            return dfs(root, prefix, 0, targetSum); // 启动DFS
//        }
//
//        public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
//            if (root == null) {
//                return 0; // 空节点，返回0
//            }
//
//            int ret = 0; // 记录以当前节点为终点的有效路径数
//            curr += root.val; // 更新当前路径和（加上当前节点值）
//
//            // 关键：检查是否存在前缀和 prev = curr - targetSum
//            ret = prefix.getOrDefault(curr - targetSum, 0);
//
//            // 将当前前缀和加入哈希表（更新出现次数）
//            prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
//
//            // 递归处理左右子树
//            ret += dfs(root.left, prefix, curr, targetSum);
//            ret += dfs(root.right, prefix, curr, targetSum);
//
//            // 回溯：当前路径结束，移除当前前缀和（计数减1）
//            prefix.put(curr, prefix.get(curr) - 1);
//
//            return ret; // 返回当前子树的有效路径总数
//        }
//    }




}
